package algorithm.array;

/**
 * leetcode : https://leetcode.com/problems/container-with-most-water/
 * Difficulty : Medium
 * Topics : Array TwoPointers
 *
 * 给一个全部是非负元素的数组，每一个数字代表水池的高度。每一个index代表宽度为1，求可以最大容纳的水的面积
 *
 * Created by yzy on 2019-09-12 17:24
 */
public class ContainerWithMostWater {

    public static void main(String[] args) {
        int[] arr = new int[]{1,8,6,2,5,4,8,3,7};
        int[] arr_2 = new int[]{1,3,2,5,25,24,5};
        int[] arr_3 = new int[]{8,10,14,0,13,10,9,9,11,11}; // answer: 80
        int[] arr_tmp = new int[]{2,3};
//        System.out.println(maxArea_optimize(arr));
        System.out.println(maxArea_optimize(arr_3));
        System.out.println(maxArea(arr_3));
    }

    /**
     * @param height
     * @return
     */
    public static int maxArea_optimize(int[] height) {
        // TODO 还未完成
        return 0;
    }

    /**
     * 穷举法,还有优化空间
     * 212ms, fastr than 9.89%
     * 40.1MB, less than 93.59%
     *
     * @param height
     * @return
     */
    public static int maxArea(int[] height) {
        int max = 0;
        int length = height.length;
        for(int i=0; i<length-1; i++){
            int lHeight = height[i];
            if(lHeight==0){
                continue;
            }

            int tmpMax = 0;
            for(int j=i+1; j<length; j++){
                int rHeight = height[j];
                int h = lHeight<rHeight ? lHeight : rHeight;
                int w = j-i;
                int area = h * w;
                tmpMax = tmpMax > area ? tmpMax : area;
            }
            max = tmpMax > max ? tmpMax : max;
        }

        return max;
    }

}
